package com.h2cloud.sort;

import java.util.ArrayList;
import java.util.Collections;

/**
 * @Package: com.h2cloud.sort
 * @ClassName: _2_selectionSort
 * @Author: h2cloud
 * @CreateTime: 2021/4/15 10:39 下午
 * @Description:
 */
public class _2_selectionSort {
    public static void main(String[] args) {
        int[] ints = myArray.get(1000);
        bucketSort(ints);
        for (int i : ints) {
            System.out.println(i);
        }
    }

    public static void bucketSort(int[] arr) {
        //最大最小值
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        int length = arr.length;

        for (int i = 0; i < arr.length; i++) {
            max = Math.max(max, arr[i]);
            min = Math.min(min, arr[i]);
        }

        //桶列表
        ArrayList<ArrayList<Integer>> bucketList = new ArrayList<>();
        for (int i = 0; i < length; i++) {
            bucketList.add(new ArrayList<>());
        }

        //最大值和最小值的差
        int diff = max - min;
        //每个桶的存数区间
        float section = (float) diff / (float) (length - 1);

        //数据入桶
        for (int i = 0; i < length; i++) {
            //当前数除以区间得出存放桶的位置 减1后得出桶的下标
            int num = (int) (arr[i] / section) - 1;
            if (num < 0) {
                num = 0;
            }
            bucketList.get(num).add(arr[i]);
        }

        //桶内排序
        for (int i = 0; i < bucketList.size(); i++) {
            // 使用jdk内置排序
            Collections.sort(bucketList.get(i));
        }

        //写入原数组
        int index = 0;
        for (ArrayList<Integer> arrayList : bucketList) {
            for (int value : arrayList) {
                arr[index] = value;
                index++;
            }
        }
    }


}
